package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-16 14:51
 */
public class SumTarget {
    public static void main(String[] args) {

    }

    /**LeetCode:494
     * 五部曲：1.下标i代表当前数字i dp[i]代表组成和i的方法数量2.递推公式：dp[i]+=dp[i=nums[j]]3.初始化：相对特殊：dp[0]=1
     * @param num
     * @return
     */
    public static int sum(int []num,int target){
        //将数组分为两部分，
        int sum=0;
        for (int i:num) {
            sum+=i;
        }
        //排除特殊情况
        if(target<0&&(-target)>sum){
            return 0;
        }
        //求组成数的方法数
        if((sum+target)/2==1){
            return  0;
        }
        int left=(sum+target)/2;
        int []dp=new int[left+1];
        dp[0]=1;
        for (int i = 0; i < num.length ; i++) {
            for(int j=left;j>=num[i];--j){
                dp[j]+=dp[j-num[i]];
            }

        }
        return dp[left];

    }
}
